package leetcode.tree;

public class Lc450_2 {

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = deleteNode(root.left, key);
        else if (key > root.val) root.right = deleteNode(root.right, key);
        else {//要删除的节点为root
            //1.删除的是根节点
            if (root.left == null && root.right == null) return null;
            //2.删除的节点有左儿子，没有右儿子
            if (root.left != null && root.right == null) return root.left;
            //3.删除的节点有右儿子，没有左儿子
            if (root.left == null && root.right != null) return root.right;
            //4.删除的节点有左右两个儿子，选右子树中最小的节点继承
            TreeNode curNode = root.right;
            while (curNode.left != null) //找到root左子树中最左边的节点，即为最小的节点
                curNode = curNode.left;
            curNode.left = root.left; //将要删除的root节点的左子树作为curNode的左儿子
            return root.right;//将root的右儿子作为root的父亲的儿子返回，也就删掉了root节点
        }
        return root;
    }

}
